
import java.text.DecimalFormat;
import java.util.ArrayList;

public class Main {
    //记录所有的指令地址集合
    public static int[] instructionsSequence = null;
    //存放转换后的页号信息
    public static int[] pagesSequence = null;
    //定义分配的内存容量
    public static int memoryBlocksNum;
    //定义地址序列的总数为400条
    public static int numOfAddress = 400;
    //定义每个页存放的大小，这里为1K，每K可以放10条指令
    public static int sizeOfPage = 1;
    public static int instructionsOfPage = sizeOfPage * 10;


    public static void main(String[] args) {
        DecimalFormat df = new DecimalFormat("0.0000");
        //生成共400个随机地址序列
        instructionsSequence = randomAddress(numOfAddress);
        //生成随机地址对应的页号序列
        pagesSequence = randomPage1(instructionsSequence,instructionsOfPage);
        System.out.println("页框数"+"  \tFIFO 命中率"+"  \tOPT 命中率"+"  \tLRU 命中率");
        //创建FIFO算法类
        FIFOReplacement FIFO = new FIFOReplacement();
        //创建OPT算法类
        OPTReplacement OPT = new OPTReplacement();
        //创建LRU算法类
        LRUReplacement LRU = new LRUReplacement();
        for (int i = 4;i<=40;i++){
            System.out.print("["+i+"]");
            memoryBlocksNum = i;//当前的页框数
            double FIFOLackRate = FIFO.replace(pagesSequence,memoryBlocksNum);
            double OPTLackRate = OPT.replace(pagesSequence,memoryBlocksNum);
            double LRULackRate = LRU.replace(pagesSequence,memoryBlocksNum);
            System.out.print("     \tFIFO:"+df.format(1-FIFOLackRate));
            System.out.print("   \tOPT:"+df.format(1-OPTLackRate));
            System.out.print("   \tLRU:"+df.format(1-LRULackRate));
            System.out.println();
        }

    }

    //合并相邻地址的页号，否则导致命中率大于50%
    public static int[] randomPage1(int[] addressSequence, int instructionsOfPage) {
        int t = -1;
        int pageNumber;
        ArrayList<Integer> pageSequence = new ArrayList<Integer>();
        for (int i = 0;i<addressSequence.length;i++){
            pageNumber = addressSequence[i]/instructionsOfPage;
            if(pageNumber!=t){
                pageSequence.add(pageNumber);
                t = pageNumber;
            }
        }
        int[] pst = new int[pageSequence.size()];
        for(int i = 0;i<pageSequence.size();i++){
            pst[i] = pageSequence.get(i);
        }
        //输出对应的页号序列
        System.out.println("对应的页号序列为（合并相邻页号）：");
        for(int i = 0 ;i< pst.length;i++){
            System.out.print(pst[i]+"\t");
            if((i+1)%20 == 0) System.out.println();
        }
        System.out.println("\n");
        return pst;
    }

    //尝试不合并相邻地址的页号
    private static int[] randomPage2(int[] addressSequence, int instructionsOfPage) {
        int pageNumber;
        ArrayList<Integer> pageSequence = new ArrayList<Integer>();
        for (int i = 0;i<addressSequence.length;i++){
            pageNumber = addressSequence[i]/instructionsOfPage;
            pageSequence.add(pageNumber);

        }
        int[] pst = new int[pageSequence.size()];
        for(int i = 0;i<pageSequence.size();i++){
            pst[i] = pageSequence.get(i);
        }
        //输出对应的页号序列
        System.out.println("对应的页号序列为（不合并相邻页号）：");
        for(int i = 0 ;i< pst.length;i++){
            System.out.print(pst[i]+"\t");
            if((i+1)%10 == 0) System.out.println();
        }
        System.out.println();
        return pst;
    }

    public static int[] randomAddress(int numOfAddress) {
        int count = 0;
        int[] address = new int[numOfAddress];
        //按照要求循环产生指令地址
        while (count < numOfAddress) {
            int ranAdr1 = (int) (Math.random() * (numOfAddress/2));
            address[count++] = ranAdr1++;
            address[count++] = ranAdr1;
            int ranAdr2 = (numOfAddress/2) + (int) (Math.random() * ((numOfAddress/2)-1));//防止最后一条指令越界
            address[count++] = ranAdr2++;
            address[count++] = ranAdr2;
        }
        System.out.println("生成的地址序列为：");
        for(int i = 0 ;i< address.length;i++){
            System.out.print(address[i]+"\t");
            if((i+1)%20 == 0) System.out.println();
        }
        System.out.println();
        return address;
    }
}
